package 迪杰斯特拉Dijkstra算法;

import java.util.Arrays;

public class 迪杰斯特拉算法2 {
	public static void main(String[] args) {
		//韩平顺版...未完成
	}
}
//定义迪杰斯特拉算法
class Dijkstra {
	//记录顶点是否访问
	int already_arr[];
	//记录顶点前一个顶点下标，关系表，动态更新
	int pre_visited[];
	//记录出发顶点到各顶点之间距离，动态更新
	int dis[];
	
	/**
	 * 构造器，初始化
	 * @param length 顶点个数
	 * @param index 出发顶点位置
	 */
	public Dijkstra(int length, int index){
		this.already_arr = new int[length];
		this.pre_visited = new int[length];
		this.dis = new int[length];
		//初始化dis数组，顶点之间距离，开始时都 填充 为最大值65535，自己设为0
		Arrays.fill(this.dis, 65535);
		this.dis[index] = 0;
		//初始化already_arr 为访问默认0，访问为1，将出发点设为 1
		this.already_arr[index] = 1;
	}
	
	//迪杰斯特拉
	public void dijkstra(char[] vertex, int[][] matrix) {
		//声明图Graph，后面用
		Graph graph = new Graph(vertex, matrix);
		
		//初始化
	}
	
}

//定义图
class Graph {
	//顶点数组
	char vertex[];
	//邻接矩阵
	int matrix[][];
	//迪杰斯特拉
	Dijkstra dijkstra;
	
	//构造器
	public Graph(char[] vertex, int[][] matrix) {
		super();
		this.vertex = vertex;
		this.matrix = matrix;
	}
	
	//迪杰斯特拉
	public void dijkstra() {
		//调用迪杰斯特拉
		dijkstra.dijkstra(vertex, matrix);
	}
	
	//输出
	public void show() {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				if(matrix[i][j] == 65535) {
					System.out.print("N");
				}else {
					System.out.print(matrix[i][j]);
				}
			}
			System.out.println();
		}
	}
	
	
}